package merge

import (
	"slices"
)

/*
计数排序（countingsort）通过统计元素数量来实现排序，通常应用于整数数组。
11.9.1 简单实现
先来看一个简单的例子。给定一个长度为𝑛的数组nums ，其中的元素都是“非负整数”，计数排序的整体流
1. 遍历数组，找出其中的最大数字，记为𝑚，然后创建一个长度为𝑚+1的辅助数组
2. 借助 counter 统计nums 中各数字的出现次数，其中
借助
counter 统计
nums 中各数字的出现次数，其中counter[num] 对应数字 num 的出现次数。
遍歷nums，每輪將counter[num] 增加 1 即可
由于 counter（數組） 的各个索引天然有序，因此相当于所有数字已经排序好了


计数排序只适用于非负整数。若想将其用于其他类型的数据，需要确保这些数据可以转换为非负整数，并且
在转换过程中不能改变各个元素之间的相对大小关系。例如，对于包含负数的整数数组，可以先给所有数字
加上一个常数，将全部数字转化为正数，排序完成后再转换回去。
计数排序适用于数据量大但数据范围较小的情况。比如，在上述示例中𝑚不能太大，否则会占用过多空间。
而当𝑛≪𝑚时，计数排序使用𝑂(𝑚)时间，可能比𝑂(𝑛log𝑛)的排序算法还要慢。
*/

type counter struct {
}

func (r counter) countingSortNaive(nums []int) {
	// 1. 统计数组最大元素 m
	m := slices.Max(nums)

	// 2. 统计各数字的出现次数
	// counter[num] 代表 num 的出现次数
	counter := make([]int, m+1)
	for _, num := range nums {
		counter[num]++
	}
	// 3. 遍历 counter ，将各元素填入原数组 nums
	for i, num := 0, 0; num < m+1; num++ {
		for j := 0; j < counter[num]; j++ {
			nums[i] = num
			i++
		}
	}
}

/*
时间复杂度为𝑂(𝑛+𝑚)、非自适应排序：涉及遍历nums和遍历counter，都使用线性时间。一般情
况下𝑛≫𝑚，时间复杂度趋于𝑂(𝑛)。
‧空间复杂度为𝑂(𝑛+𝑚)、非原地排序：借助了长度分别为𝑛和𝑚的数组res和counter。
‧稳定排序：由于向res中填充元素的顺序是“从右向左”的，因此倒序遍历nums可以避免改变相等元
素之间的相对位置，从而实现稳定排序
*/
func (r counter) countingSort(nums []int) {
	//1.统计数组最大元素m
	m := slices.Max(nums)
	//2.统计各数字的出现次数
	//counter[num]代表num的出现次数
	counter := make([]int, m+1)
	for _, num := range nums {
		counter[num]++
	}
	//3.求counter的前缀和，将“出现次数”转换为“尾索引”
	//即counter[num]-1是num在res中最后一次出现的索引

	//计数数组：[0, 1, 2, 2, 1, 0, 0, 0, 1]
	//count[1] = 1
	//count[2] = 1 + 2 = 3
	//count[3] = 3 + 2 = 5
	for i := 0; i < m; i++ {
		//将计数数组中的值累加，得到每个元素的最终位置：
		counter[i+1] = counter[i] + counter[i+1]
	}
	//4.倒序遍历nums，将各元素填入结果数组res
	//初始化数组res用于记录结果
	n := len(nums)
	res := make([]int, n)
	for i := n - 1; i >= 0; i-- {
		num := nums[i]
		//将num放置到对应索引处
		res[counter[num]-1] = num
		//令前缀和自减1，得到下次放置num的索引
		counter[num]--
	}
	//使用结果数组res覆盖原数组nums
	copy(nums, res)
}
